package 算法.NiuKe.JZ;

/**
 * @author:谢君臣
 * @Date:2021/4/2820:38
 * @version:1.0
 * @function: 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，
 * 每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
 */
public class JZ66 {
    public static void main(String[] args) {
        System.out.println(hasPath(new char[][]{
                {'A', 'B', 'C'},
                {'B', 'E', 'D'},
                {'F', 'D', 'E'},
        }, "ABCDEBF"));
    }
    public boolean hasPath1 (char[][] matrix, String word) {
        int rows = matrix.length;
        if (rows == 0) return false;
        int cols = matrix[0].length;
        boolean[][] visited = new boolean[rows][cols];//标识每个方格是否在路径里面，防止路径进入重复的方格里
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (hasPath (matrix,i,j,visited,word,0)) return true;
            }
        }
        return false;
    }

    public boolean hasPath (char[][] matrix,int row,int col,boolean[][] visited,String word,int loc) {
        if (loc == word.length()) return true;
        int rows = matrix.length;
        int cols = matrix[0].length;
        if (row < 0 || row == rows || col < 0 || col == cols) return false;
        if (visited[row][col]) return false;
        if (matrix[row][col] == word.charAt(loc)){
            visited[row][col] = true;
            if (hasPath (matrix,row-1,col,visited,word,loc+1) || hasPath (matrix,row+1,col,visited,word,loc+1)
                    || hasPath (matrix,row,col-1,visited,word,loc+1) || hasPath (matrix,row,col+1,visited,word,loc+1)){
                return true;
            }
            visited[row][col] = false;
        }
        return false;
    }

    public static boolean hasPath(char[][] matrix, String word) {
        // write code here
        int[][] path = null;
        char[] route = word.toCharArray();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                path = new int[matrix.length][matrix[0].length];
                if (matrix[i][j] == route[0]) {
                    if (checkPath(path, i, j, matrix, route.clone(), 0))
                        return true;
                }
            }
        }
        return false;
    }

    private static boolean checkPath(int[][] path, int i, int j, char[][] matrix, char[] route, int k) {
        if (k >= route.length) {
            return true;
        } else {
            if (i >= 0 && i < matrix.length && j >= 0 && j < matrix[0].length && path[i][j] == 0 && matrix[i][j] == route[k]) {
                path[i][j] = 1;
                k++;
                int[][]temp = path.clone();
                boolean b = checkPath(temp, i + 1, j, matrix, route, k);
                if (!b){temp = path.clone(); b = checkPath(temp, i - 1, j, matrix, route, k);}
                if (!b){temp = path.clone(); b = checkPath(temp, i, j + 1, matrix, route, k);}
                if (!b){temp = path.clone(); b = checkPath(temp, i, j - 1, matrix, route, k);}
                return b;
            } else
                return false;
        }
    }
}
